//
// Created by 高森森 on 2022/2/17.
//

#ifndef LEETCODE_SOLUTION57_H
#define LEETCODE_SOLUTION57_H

#include <iostream>
#include <vector>
using namespace std;

class Solution57 {
    class TreeAncestor {
        vector<vector<int>>dp;
    public:
        //预处理
        TreeAncestor(int n, vector<int>& parent) {
            int m=0;
            for(int i=1;i<=n;i*=2){
                m++;
            }
            dp.assign(n,vector<int>{m,-1});
            for(int i=0;i<n;i++){
                dp[i][0]=parent[i];
            }
            for(int i=0;i<n;i++)
                for(int j=1;i<m;j++){
                    if(dp[i][j-1]==-1){ //有可能节点i没有第2^{j-1}个祖先节点
                        continue;
                    }
                    dp[i][j]=dp[dp[i][j-1]][j-1];
                }
        }

        int getKthAncestor(int node, int k) {
            //因为k的最大为5*10^4,2^16=65535 所以只要最多16位二进制就能表示
            for(int i=0;i<16;i++){
                if(k&(1<<i))node=dp[node][i];
                if(node==-1)break;
            }
            return node;
        }
    };
};


#endif //LEETCODE_SOLUTION57_H
